package linkedlist;

public class MyDLinkedList {
    static class Node{
        public String val;
        public Node prev = null;
        public Node next = null;

        public Node(String val){
            this.val = val;
        }
    }

    //表示整个链表，此处不引入傀儡节点，使用null表示空的链表
    private Node head = null;
    //为了方便后续实现尾插操作
    private Node tail = null;

    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (Node cur = head; cur != null; cur = cur.next){
            stringBuilder.append(cur.val);
            if (cur.next != null){
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    //实现链表的一些核心操作
    //头插
    public void addFirst(String val){
        Node newNode = new Node(val);
        if (head == null){
            //链表为空
            head = newNode;
            tail = newNode;
        }else {
            //链表不为空，让新节点和原来的头节点建立好关联关系
            newNode.next = head;
            head.prev= newNode;
            //让head指向新节点
            head = newNode;
        }
    }

    //尾插
    public void addLast(String val){
        Node newNode = new Node(val);
        if (head == null){
            //链表为空
            head = newNode;
            tail = newNode;
        }else {
            //链表不为空，让新节点和原来的尾节点建立好关联关系
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    //获取链表长度
    public int size(){
        int size = 0;
        for (Node cur = head; cur != null; cur = cur.next){
            size ++;
        }
        return size;
    }

    //中间任意位置插入，根据index下标，插入到合适的位置上
    public void add(int index, String val){
        if (index < 0 || index > size()){
            throw new IndexOutOfBoundsException("Index" + index + ", Size" +size());
        }
        //如果index为0，说明是头插
        if (index == 0){
            addFirst(val);
            return;
        }
        //如果index为size，说明是尾插
        if (index == size()){
            addLast(val);
            return;
        }
        //处理中间的一般情况
        //根据index下标，找到待插入位置的前一个位置，前一个元素的下标index-1
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        //经过上述循环，prev已经指向待插入节点的前一个位置了
        //把后一个节点的位置也记录出来
        Node next = prev.next;

        //新节点的插入，就是要放到prev和next之间
        Node newNode = new Node(val);
        //建立prev和newNode的关联关系
        prev.next = newNode;
        newNode.prev = prev;
        //建立newNode和next之间的关联关系
        newNode.next = next;
        next.prev = newNode;
    }

    //判定其元素是否存在
    public boolean contains(String val){
        //遍历链表，看val是否存在，存在返回true，不存在返回false
        for (Node cur = head; cur != null; cur = cur.next){
            if (cur.val.equals(val)){
                return true;
            }
        }
        return false;
    }

    //查找元素，返回该元素的下标，如果没找到，返回-1
    public int indexOf(String val){
        int index = 0;
        for (Node cur = head; cur != null; cur = cur.next){
            if (cur.val.equals(val)){
                return index;
            }
        }index++;
        return -1;
    }

    //删除头部元素
    public void removeFirst(){
        if (head == null){
            //空链表不需要删除
            return;
        }
        //针对只有一个节点的情况特殊处理
        if (head.next == null){
            head = null;
            tail = null;
            return;
        }
        head = head.next;
        head.prev = null;
    }

    //删除尾部元素
    public void removeLast(){
        if (head == null){
            //空链表 不需要删除
            return;
        }
        if (head.next == null){
            //只有一个节点，特殊处理
            head = null;
            tail = null;
            return;
        }
        tail = tail.prev;
        tail.next = null;
    }

    //指定位置删除
    private void remove(int index){
        if (index < 0 || index >= size()){
            throw new IndexOutOfBoundsException("Index" + index + ", Size:" +size());
        }
        if (index == 0){
            //头删除
            removeFirst();
            return;
        }
        if (index == size() - 1){
            //尾删
            removeLast();
            return;
        }
        //一般情况，找到待删除节点的前一个位置，index - 1的位置
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        //循环结束，prev就指向带删除元素的前一个位置
        //toRemove就是要删除的元素
        Node toRemove = prev.next;
        //指向待删除元素的下一个位置
        Node next = toRemove.next;

        prev.next = next;
        next.prev = prev;
    }

    //指定值删除
    public void remove(String val){
        if (head == null){
            return;
        }
        //判定头删/尾删特殊情况
        if (head.val.equals(val)){
            removeFirst();
            return;
        }
        if (tail.val.equals(val)){
            removeLast();
            return;
        }
        //一般情况，遍历链表，找到带删除元素的位置
        Node toRemove = null;
        for (; toRemove != null; toRemove = toRemove.next){
            if (toRemove.val.equals(val)){
                break;
            }
        }
        //通过上述循环，此时toRemove就指向了待删除元素
        if (toRemove == null){
            //要删除的值在链表中不存在
            return;
        }
        //真正进行删除
        Node prev = toRemove.prev;
        Node next = toRemove.next;
        //重新构建prev和next之间的关系
        prev.next = next;
        next.prev = prev;
    }

    //清空链表
    public void clear(){
        head = null;
        tail = null;
    }

    private static void test1() {
        MyDLinkedList list = new MyDLinkedList();
        list.addFirst("a");
        list.addFirst("b");
        list.addFirst("c");
        list.addFirst("d");
        System.out.println(list);
    }

    private static void test2() {
        MyDLinkedList list = new MyDLinkedList();
        list.addLast("a");
        list.addLast("b");
        list.addLast("c");
        list.addLast("d");
        System.out.println(list);
    }

    private static void test3() {
        MyDLinkedList list = new MyDLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        list.add(3, "x");
        // 预期结果: [a, b, c, x, d]
        System.out.println(list);
    }

    private static void test4() {
        MyDLinkedList list = new MyDLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        System.out.println(list.contains("a"));
        System.out.println(list.contains("x"));
        System.out.println(list.indexOf("c"));
        System.out.println(list.indexOf("x"));
    }

    private static void test5() {
        MyDLinkedList list = new MyDLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        list.removeFirst();
        System.out.println(list);
        list.removeFirst();
        System.out.println(list);
        list.removeFirst();
        System.out.println(list);
        list.removeFirst();
        System.out.println(list);
    }

    private static void test6() {
        MyDLinkedList list = new MyDLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        list.removeLast();
        System.out.println(list);
        list.removeLast();
        System.out.println(list);
        list.removeLast();
        System.out.println(list);
        list.removeLast();
        System.out.println(list);
    }

    public static void test7() {
        MyDLinkedList list = new MyDLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        list.remove(3);
        System.out.println(list);
        list.remove(1);
        System.out.println(list);
        list.remove(0);
        System.out.println(list);
    }

    private static void test8() {
        MyDLinkedList list = new MyDLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(2, "c");
        list.add(3, "d");
        list.remove("b");
        System.out.println(list);
    }
    public static void main(String[] args) {
         test1();
         test2();
         test3();
         test4();
         test5();
         test6();
         test7();
         test8();
    }
}
